package Sort;

import java.util.Arrays;
import java.util.PriorityQueue;

// Lettcode 215: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
public class findKthLargest {
    public static void main(String[] args) {
        int[] nums = new int[] {3,2,3,1,2,4,5,5,6};
        int k = 4;
        System.out.println(new findKthLargest().findKthLargest(nums, k));
    }

    // 1. 直接对nums[]数组进行排序。
//    public int findKthLargest(int[] nums, int k) {
//        Arrays.sort(nums);
//        return nums[nums.length - k];
//    }

    // 2.利用小顶堆，维护堆的大小，进行排序
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int val: nums) {
            priorityQueue.add(val);
            if (priorityQueue.size() > k)
                priorityQueue.poll();
        }
        return priorityQueue.peek();
    }
}
